Poor man's bilinear

Skal/Bomb!

Before everyone, eventually, stops using color-mapped video modes, let's look back at an old way of faking colors when you only have few: dithering. This small text is intended for beginners, so mature coders should give a way. :)

Suppose you only have two colors, C1 and C2, and would like to blend them (50%) on the screen. If you don't have, on your palette, the corresponding half-way color (C1+C2)/2, you can anyway resort to sacrifying space resolution in order to enhance color resolution: just plot colors C1 and C2 alternatively. Far from the screen (or on a big screen :)), such nearby colors will appear blended. Frown your eyelids, in case. :) The overall color will look like being (C1+C2)/2, when spatially averaged by your eyes. For instance, if you could double your screen's resolution, drawing the following 2x2 pattern:

+---+---+
|C1 | C2|
+---+---+
|C2 | C1|
+---+---+

might somehow replace the drawing of the single 1x1 pixel with the blended color.

Now, there's a way systematically performing this pattern-based dithering for any blending factor.

Consider drawing a full scanline with a "color" blended from C1 and C2 with a factor x. Namely, you'd like to draw color C = (1-x)*C1 + x*C2. On this scanline, x percent of the pixels will need being drawn with color C1 (and the rest with C2) in order to have the previous spatial averaging work. A way of choosing between C1 and C2 with the correct ratio is to simply add a random value, between 0.0 and 1.0, to x: if the result is greater than 1.0, then use color C2. Otherwise, use color C1. You can easily figure out why it works.

This scheme has several inconveniences: it uses floats, needs a random generator, and produces a rather unpredictable random visual result. These issues are (to a certain point) adressed by using a matrix with special, fixed, "random" values in fixed-point format. These values are chosen in order to spread the error best and give a stable visual result. For instance, consider the matrix:

+----+----+
|0x00|0x80|
+----+----+
|0xc0|0x40|
+----+----+

or, better:

+----+----+----+----+
|0x00|0x80|0x20|0xa0|
+----+----+----+----+
|0xc0|0x40|0xe0|0x60|
+----+----+----+----+
|0x30|0xb0|0x10|0x90|
+----+----+----+----+
|0xf0|0x70|0xd0|0x50|
+----+----+----+----+

They contain equally distributed values (between 0x00 and 0x100), intertwined in a rather efficient manner (adjacent figures in the matrix are not "too close" from each other). You can build bigger such matrix by replicating 4 times the above one, and using some offset on each quarters.

Now, using these matrix is easy: make your blending factor go 8-bit fixed-point (X=(int)(x*256)), build a two-elements array A[2] = {C1, C2} with the color indexes of the palette, and compute the color to plot at position x,y with:

Color = A[ ( X + Matrix[y%4][x%4] )>>8 ];

(if Matrix[][] is the above 4x4 one).

At this point, I must agree that it seems a rather artificial and unpractical dithering method. But, it surprisingly fits rather well the bilinear filtering of texture mapping: the previous array A[] is the (color-mapped) texture map and the blending factors X are the U or V texture mapping coordinates.

Most probably, your U-V coordinates are already in fixed-point format (along with their gradient), so that your inner loop looks something like:

          unsigned short U, V, dU, dV;
           /* init ... */
          for(i=0; i>8) ];
            U += dU; V += dV;
          }

if U and V are in 8:8 fixed point format.

You indeed only have few things to change to plug the dithering in:

                // j is the y-coordinate of the scanline
          for(i=0; i>8) ];
            U += dU; V += dV;
          }

and that's it!

There are other cases where this dithering technique applies. For instance: streching a bitmap (the blending factors are related to the ratio old_width/new_width and old_height/new_height).

You can have a look at (and play with) the C-sample file 'bil.c'. It builds a plasma mapped with a very small 16x16 texture and interpolate it with the above. Have a look at the header for various Linux/Dos compilation flags. I did not removed debugging code from it, so there's more than meet the eyes in there (rotozoom, per-block interpolation, etc...) -> look at the sources.

Take care, and see you at the LTP4...

Skal/Bomb!
skal@planet-d.net
Tue Jul 18 GMT 2000

PS: Btw, did you have a look at Unreal Tournament's software bilinear filtering, lately? :)